AGC 012 题解
$B$
$t_{i, j}$ 表示把距离 $i$ 为 $j$ 的区域染色的最晚指令，每次把 $t_{i, j}$ 转给 $t_{x, j - 1}$ 其中 $x$ 和 $i$ 相邻。$O(d(n + m))$
$C$
巧妙的构造，考虑分为两半，后半是 $1$ ~ $100$，前半是 $1$ ~ $x$ 的排列，好串数量即为前半部分上升序列的个数。考虑进空串就是构造个数为 $n + 1$ 的。考虑从小到 $x$ 加字符，每次可以放在结尾或开头，对应的答案每次 $*2$ 或 $+1$。
$D$
这关系显然具有传递性。。即如果 $a$ 能到达位置 $i$，能和 $a$ 交换的 $b$ 也能到达 $i$。那么缩块，每个连通块分别独立。
一个连通块的答案是 $\frac{(\sum s_i)!}{\prod s_i!}$，$s_i$ 表示该连通块中颜色为 $i$ 的点数。
考虑如何连边：每种颜色向其重量最小的球连边，每个重量最小的球向全局重量最小球连边（如果两者颜色相同就只能找全局次小球）
最后只有全局最小球所在的块的颜色可能 $> 1$（显然 $= 1$ 就没有贡献）。
$E$
跳跃只能使用 $log$ 次。而你如果“固步自封”就只能走一个连续区间。预处理每种长度的区间。
抽象一点看，是从 $log$ 层每层不选或选一个区间看能不能覆盖所有位置。由于没有顺序要求，我们考虑维护前后缀的 dp。
- $l_S$ 表示使用了 $S$ 长度集合，能完全覆盖到的最右端点
- $r_S$ 表示使用了 $S$ 长度集合，能完全覆盖到的最左端点
- $L_{d, x}$ 表示第 $d$ 层中 $x$ 所在区间的左端点
- $R_{d, x}$ 表示第 $d$ 层中 $x$ 所在区间的右端点
转移就枚举长度、枚举区间，更新 $l$ 和 $r$，复杂度是 $O(V log V log(区间个数))$
这样会不会爆炸啊？$\mathcal{Naive}$！区间个数如果在长度最大的那层超过 $logV$ 了那就直接无解了啊。
$F$
首先 $b_n$ 是确定的，删去它。然后需要选 $2$ 个 $a$ 中元素一块删去。我们发现 $b_{n - 1}$ 最多移动 $1$！
可以推一些结论:
- $a_i \leq b_i \leq a_{2n - i}$
- 不存在 $i < j$ 使得 $b_j < b_i < b_{j + 1}$
大概是充要条件？
所以 $b_i$ 的取值范围就是 $[a_i, \min(b_j)] \cup [\max(b_j), a_{2n - i}]$（要用到第二条性质，所有 $b_j$ 都是连贯的）。设两个集合分别为 $A$ 和 $B$。
后面的限制前面的，考虑从后往前 dp。$A.l$、$A.r$ 递减，$B.l$、$B.r$ 递增。维护可选空位集合，需要支持每次插入/删除后的去重排序操作，等价于「加首尾」和「删除 $b_{i + 1}$ 到 $b_i$ 这段区间」（不包括端点），显然每个 $b_i$ 都在边界上。
按此设计 dp 方程：$dp_{i, j, k}$ 表示选定 $b_i$ 后，$A$ 还剩 $j$ 个空位，$B$ 还剩 $k$ 个空位。转移就枚举选哪个空位。
坑点：如果选择拓宽某一方向，另一方向的空位数需要额外加一，因为每次删除的区间不包括端点，$b_{i + 1}$ 的位置需要空出来。